#include<iostream>
#include<queue>
using namespace std;

class Solution
{
    int m{}, n{};
    bool visit[101][101]{};
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
public:
    bool exist(vector<string>& board, string word)
    {
        m = board.size(), n = board[0].size();
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(board[i][j]==word[0])
                {
                    if(dfs(board, i, j, word, 0))
                        return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<string>& board, int i, int j, string& word, int pos)
    {
        if(pos == word.size()-1)
            return true;
        visit[i][j] = true;
        for(int k=0; k<4; k++)
        {
            int x = i+dx[k], y = j+dy[k];
            if(x>=0 && x<m && y>=0 && y<n && visit[x][y]==false && board[x][y]==word[pos+1])
            {
                if(dfs(board, x, y, word, pos+1))
                    return true;
            }
        }
        visit[i][j] = false;//这条路没走通，不能堵死后续还会找到他的可能性
        return false;
    }
};
